Алгоритм Евклида

Алгоритм Евклида HОК(а,б) = а*б/HОД(а,б)
HОД(а,б) определяется по алгоритму Евклида:
Алгоритм 1

while (a<>b) do
  begin
   if a > b then a := a - b
            else b := b - a;
  end;
 HОД := a;

Алгоритм 2

{Будем считать , что HОД
(0,0) = 0. Тогда HОД (a,b) = HОД (a-b,b)  =  HОД  (a,b-a);  HОД
(a,0) = HОД (0,a) = a для всех a,b>=0. }
 m := a; n := b;
{инвариант: HОД (a,b) = HОД (m,n); m,n >= 0 }
 while not ((m=0) or (n=0)) do 
  begin
   if m >= n then 
    begin
     m := m - n;
    end else 
     begin n := n - m; end;
    end;
 if m = 0 then begin k := n; end else 
  begin k := m;end;
  {NOD (a,b)=k}

Более интересен для расмотрения второй алгоритм, так как при внесении незначительных изменений мы получим новую задачу. Но для начала следует заметить, что этот алгоритм можно ускорить заменив вычитание на деление с остатком.

 m := a; n := b;
 while not ((m=0) or (n=0)) do 
  begin
   if m >= n then 
    begin
     m := m mod n;
    end else 
     begin n := n mod m; end;
    end;
 if m = 0 then begin k := n; end else 
  begin k := m;end;

Мы получили очень большой выйгрыш по времени. Если не верите можете проверить сами на простом примере а=1000000000;b=1, на обычном компьютере результата с первым алгоритмом вы дождётесь нескоро, а вот второй алгоритм выдаст результат моментально.

Но давайте перейдем к обещанной задачи, а точнее решение Диофантового уравнения. Для тех, кто не знает "Диофантовы уравнения" - это уравнения вида Ax+By=C, где A,B,C целые числа и требуется найти целые решения x,y.
Как ни странно, эта задача решается с помощь алгоритма Евклида.
Прежде всего при помощи него можно найти D = НОД(a,b);Следовательно имеет место уравнение:

Ak + Bl = D

Если D=C, то найдено одно из решений X = k; Y = l;

Вообще, если С = D*q, то A*(kq) + B(*lq) = D*q = C;

Следовательно решение существует только когда C кратно D.

{Даны натуральные а и b, не равные 0  одновременно.
Hайти d = HОД (a,b) и такие целые x и y, что d = a*x + b*y.

     Решение.  Добавим в алгоритм Евклида переменные p, q, r, s
и впишем в инвариант условия m = p*a + q*b; n = r*a + s*b.}

        m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
        {инвариант: HОД (a,b) = HОД (m,n); m,n >= 0
                    m = p*a + q*b; n = r*a + s*b.}
        while not ((m=0) or (n=0)) do begin
          if m >= n then begin
            m := m - n; p := p - r; q := q - s;
          end else begin
            n := n - m; r := r - p; s := s - q;
          end;
        end;
        if m = 0 then begin
          k :=n; x := r; y := s;
        end else begin
          k := m; x := p; y := q;
        end;

Зная частное решение (X,Y) можно найти все остальные

        X_r=X+(B*r)/(НОД(A,B));
        Y_r=Y-(A*r)/(НОД(A,B));

Попробуйте переделать алгоритм так, чтобы вместо вычитания использовать деление с остатком.

Попробуйте написать вариант алгоритма Евклида, использующий соотношения

      HОД(2*a, 2*b) = 2*HОД(a,b)
      HОД(2*a, b)   =   HОД(a,b) при нечетном b,

не включающий деления с остатком, а использующий лишь деление на 2 и проверку четности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.)

Решение.

  m:= a; n:=b; d:=1;
  {HОД(a,b) = d * HОД(m,n)}
  while not ((m=0) or (n=0)) do begin
    if (m mod 2 = 0) and (n mod 2 = 0) then begin
      d:= d*2; m:= m div 2; n:= n div 2;
    end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
      m:= m div 2;
    end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
      n:= n div 2;
    end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin
      m:= m-n;
    end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin
      n:= n-m;
    end;
  end;
  {m=0 => ответ=d*n; n=0 => ответ=d*m}

Оценка числа действий: каждое второе действие делит хотя бы одно из чисел m и n пополам.

Сайт управляется системой uCoz